package algorithm.tree.bst;

import java.util.Random;

/**
 * 二叉树是一种符号表，符号表应该满足一下几个规定
 * 1.没有重复值
 * 2.键不能为null
 * 实现一个二分查找树
 */
public class BST implements FuhaoBiaoI<Entity> {

  public TreeNode root;

  public int count;

  @Override
  public void put(Entity value) {
    count++; //插入加一
    int key = value.key;
    if (root != null) {
      TreeNode root = this.root;
      while (true) {
        TreeNode nextroot;//下一层node
        if (key > root.value.key) {
          root.n++;
          nextroot = root.right;
          if (nextroot == null) { //插入了可以退出
            root.right = new TreeNode(value);
            break;
          } else {
            root = root.right;
          }
        } else if (key < root.value.key) {
          root.n++;
          nextroot = root.left;
          if (nextroot == null) { //插入了可以退出
            root.left = new TreeNode(value);
            break;
          } else {
            root = root.left;
          }
        } else {
          //相等的话 就更新
          root.value = value;
          //只是更新的话，请总数 -1
          count--;
          break;//更新了直接退出
        }

      }


    } else {
      root = new TreeNode(value);
    }
  }

  @Override
  public void delete() {

  }

  //以当前节点为根节点，获取最小的节点
  public TreeNode min(TreeNode root){

    return null;
  }

  @Override
  public void get() {

  }

  @Override
  public int size() {
    return size(root);
  }

  public int size(TreeNode root) {

    return count;
  }

  public static void main(String[] args) {
    //测试插入
    BST bst = new BST();
    //声明
    Random random = new Random();
    for (int i = 0; i < 10; i++) {
      int i1 = random.nextInt(2000);
      Entity entity = new Entity(i1, "2");
      bst.put(entity);
    }
    System.out.println("节点数: "+bst.count);
  }

}

